/**
 * 53. 最大子数组和
 * 【中等】
 *
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * `子数组` 是数组中的一个连续部分。
 *
 * 示例 1：
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 *
 * 示例 2：
 * 输入：nums = [1]
 * 输出：1
 *
 * 示例 3：
 * 输入：nums = [5,4,-1,7,8]
 * 输出：23
 */

const maxSubArray = (nums: number[]): number => {
	let ans = -Infinity
	let sum = 0
	for (let i = 0; i < nums.length; i++) {
		sum += nums[i]
		ans = Math.max(ans, sum)

		// 重点的一步执行
		if (sum <= 0) sum = 0
	}

	return ans
}

/**
 * 分治
 * 思路：不断分割，直到每个部分是一个数字为止，然后不断合并，返回左右和左右合并之后，3个最大子序和中的最大的一个
 * 复杂度：时间复杂度O(nlogn)，二分复杂度O(logn)，二分之后每一层统计左右和合并之后的最大子序和复杂度是O(n)，所以之后的复杂度是O(nlogn)。空间复杂度O(logn)，递归的栈空间，因为是二分，每次数据规模减半
 */
{
	const maxSubArray = (nums: number[]): number => {
		return _maxSubArray(nums, 0, nums.length - 1)
	}

	function _maxSubArray(nums, start, end) {
		if (start === end) {
			//递归终止条件
			return nums[start]
		}

		const mid = start + Math.floor((end - start) / 2)
		const lSum = _maxSubArray(nums, start, mid) // 左边最大子序和
		const rSum = _maxSubArray(nums, mid + 1, end) // 右边最大子序和
		const cross = crossSum(nums, start, mid, end) // 合并左右的之后的最大子序和

		return Math.max(lSum, rSum, cross)
	}

	function crossSum(nums, start, mid, end) {
		if (start === end) return nums[start]

		let lMaxSum = Number.MIN_SAFE_INTEGER
		let lSum = 0
		for (let i = mid; i >= start; i--) {
			lSum += nums[i]
			lMaxSum = Math.max(lMaxSum, lSum)
		}

		let rMaxSum = Number.MIN_SAFE_INTEGER
		let rSum = 0
		for (let i = mid + 1; i <= end; i++) {
			rSum += nums[i]
			rMaxSum = Math.max(rMaxSum, rSum) //更新右边最大子序和
		}

		return lMaxSum + rMaxSum //返回左右合并之后的最大子序和
	}
}
